#include <cinttypes>

class LLRB
{
private:
    typedef int32_t rb_key;
    typedef int32_t rb_value;
    typedef int32_t rb_size;
    typedef bool rb_color;
    #define RED true
    #define BLACK false
private:
    struct Node
    {
        rb_key key{ 0 };
        rb_value value{ 0 };
        Node* left{ nullptr };
        Node* right { nullptr };
        rb_color color{ RED };
        //rb_size size{ 1 };

        Node() = default;
        Node(rb_key k, rb_value v)
        {
            key = k;
            value = v;
        }
    };
private:
    Node* nil_{ nullptr };
    Node* root_{ nullptr };
public:
    LLRB()
    {
        nil_ = new Node();
        nil_->left = nil_->right = nil_;
        root_ = nullptr;
    }
    ~LLRB()
    {
        delete(root_);
        delete(nil_);
    }
public:
    rb_value get(Node* h, rb_key key)
    {
        if (h == nil_)   return -1;
        if (key == h->key)  return h->value;
        if (key < h->key)   return get(h->left, key);
        else                return get(h->right, key);
    }
    void insert(rb_key key, rb_value value)
    {
        root_ = _insert(root_, key, value);
        if (is_red(root_)) root_->color = !root_->color;
    }
    void erase(rb_key key)
    {
        root_ = _erase(root_, key);
        root_->color = BLACK;
    }
private:
    bool is_red(Node* h)
    {
        return h != nil_ && h->color == RED;
    }
    void color_flip(Node* h)
    {
        h->color        = !h->color;
        h->left->color  = !h->left->color;
        h->right->color = !h->right->color;
    }
    Node* rotate_left(Node* h)
    {
        Node* x = h->right;
        h->right = x->left;
        x->left = h;
        x->color = x->left->color;
        x->left->color = RED;
        return x;
    }
    Node* rotate_right(Node* h)
    {
        Node* x = h->left;
        h->left = x->right;
        x->right = h;
        x->color = x->right->color;
        x->right->color = RED;
        return x;
    }
    Node* fix_up(Node* h)
    {
        if (is_red(h->right))
            h = rotate_left(h);
        if (is_red(h->left) && is_red(h->left->left))
            h = rotate_right(h);
        if (is_red(h->left) && is_red(h->right))
            color_flip(h);
        return h;
    }
    Node* move_red_left(Node* h)
    {
        color_flip(h);
        if (is_red(h->right->left))
        {
            h->right = rotate_right(h->right);
            h = rotate_left(h);
            color_flip(h);
        }
        return h;
    }
    Node* move_red_right(Node* h)
    {
        color_flip(h);
        if (is_red(h->left->left))
        {
            h = rotate_right(h);
            color_flip(h);
        }
        return h;
    }
    rb_key _min(Node* h)
    {
        while (h->left != nil_) h = h->left;
        return h->key;
    }
    rb_key _max(Node* h)
    {
        while (h->right != nil_) h = h->right;
        return h->key;
    }
    Node* _insert(Node* h, rb_key key, rb_value value)
    {
        if (!h)
        {
            Node* x = new Node(key, value);
            x->left = x->right = nil_;
            return x;
        }
        
        if (key == h->key)      h->value = value;
        else if (key < h->key)  h->left = _insert(h->left, key, value);
        else                    h->right = _insert(h->right, key, value);

        return fix_up(h);
    }
    Node* _erase(Node* h, rb_key key)
    {
        if (key < h->key)
        {
            if (!is_red(h->left) && !is_red(h->left->left))
                h = move_red_left(h);
            h->left = _erase(h->left, key);
        }
        else
        {
            if (is_red(h->left))
                h = rotate_right(h);
            if (!is_red(h->right) && is_red(h->right->left))
                h = move_red_right(h);
            if (key == h->key)
            {
                rb_key min_key = _min(h->right);
                h->value = get(h->right, min_key);
                h->key = min_key;
                h->right = _erase(h->right, key);
            }
            else
            {
                h->right = _erase(h->right, key);
            }
            
        }
        return fix_up(h);
    }
};